#define _CRT_SECURE_NO_WARNINGS

//34. 在排序数组中查找元素的第一个和最后一个位置
//二分查找

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0) return {-1, -1};
        //左端点
        int begin = 0;
        int left = 0, right = nums.size() -1 ;
        while(left < right)
        {
            int mid = left + (right - left) / 2; 
            //找左端点
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        //判断是否有结果,left/right判断都可以
        if(nums[left] != target) return {-1, -1};
        else begin = left;

        //开始找右端点
        //可以直接在左端点的基础上寻找，即left已经确定，不需要left = 0;
        right = nums.size() -1;
        while(left < right)
        {
            int mid = left + (right - left + 1)/ 2;
            if(nums[mid] > target) right = mid -1;
            else left = mid;
        }
        return {begin, right};
    }
};